from typing import List

# 方法一：选 or 不选 问题
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        path = []
        # 选 or 不选 问题
        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return
            # 剪枝，如果层数达到满层，或者容量为0
            if i == len(candidates) or left < 0:
                return
            # 不选
            dfs(i + 1, left)
            # 选
            path.append(candidates[i])
            dfs(i, left - candidates[i])
            path.pop()  # 恢复现场
        dfs(0, target)
        return ans

# 方法二：选哪个问题
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            if left < candidates[i]:
                return

            # 枚举选哪个
            for j in range(i, len(candidates)):
                path.append(candidates[j])
                dfs(j, left - candidates[j])
                path.pop()  # 恢复现场

        dfs(0, target)
        return ans
